package dataStructure.other;

/**
 * @author: vince_zww
 * @date: 2019/9/19 9:59
 * @desceription: 链表——单链表的操作：插入，删除，查询
 */
public class LinkedList {
    //自定义的结点
    public Node head;

    /**
     * 插入
     */
    public void insertTail(int value){
        Node node = new Node(value,null);
        if (head == null){
            head = node;
        }else {
            Node q = head;
            //找到最后next一个不为空的结点并赋值
            while(q.next !=null){
                q = q.next;
            }
            //注意，顺序不可反，否者链表就断开了
            node.next = q.next;
            q.next = node;
        }
    }

    /**
     * 删除
     */
    public void deleteByNode(int value){
        if (head == null){
            return;
        }
        Node p = head;
        Node q = null;
        //从链表中找到要删除的value
        while (p!=null && p.data != value){
            q = p;
            p = p.next;
        }
        if (p==null){
            return;
        }
        //第一个就是要删除的结点
        if (q==null){
            head = head.next;
        }else {
            //删除结点，其实就是把要删除的值prev结点指向他的next结点
            q.next = q.next.next;
            //然后java自动内存管理
        }
    }

    /**
     * 根据下标查询
     */
    public Node findByIndex(int index){
        Node p = head;
        int pos = 0;
        while (p != null && pos != index){
            p = p.next;
            ++pos;
        }
        return p;
    }

    /**
     * 根据值查询
     */
    public Node findByValue(int value){
        Node p = head;
        while (p != null && p.data != value){
            p=p.next;
        }
        return  p;
    }

    /**
     * 输出链表
     */
    public void printAll(){
        Node p=head;
        while (p != null){
            System.out.print(p.data);
            p = p.next;
            if(p != null){
                System.out.print("->");
            }
        }
        System.out.println();
    }

    /**
     * 结点是否存在
     */
    public void print(Node node){
        if (node != null){
            System.out.println("查找结果："+node.data);
        }else {
            System.out.println("不存在");
        }
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        for (int i = 0; i < 8; i++) {
            //插入数据
            linkedList.insertTail(i);
        }
        linkedList.printAll();
        //删除
        linkedList.deleteByNode(7);
        linkedList.printAll();
        Node node1 = linkedList.findByIndex(4);
        linkedList.print(node1);
        Node node2 = linkedList.findByValue(2);
        linkedList.print(node2);
        Node node3 = linkedList.findByValue(50);
        linkedList.print(node3);
    }




}
